package com.ztom.v2;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangTao
 */
public class Code61PalindromePartitioning {

    public List<List<String>> partition(String s) {
        if (s == null || s.isEmpty()) {
            return new ArrayList<>();
        }
        List<List<String>> res = new ArrayList<>();
        dfs(s, 0, new LinkedList<>(), res);
        return res;
    }

    /**
     * 对于连续型（如本题），我们要挑选的是一个连续的子集，要考虑的是该子集的结束位置
     * 而对于离散型（如幂集那道题），我们要挑选的是单个元素加入子集，要考虑的是该元素是否加入子集
     *
     * @param s
     * @param index
     * @param path
     * @param res
     */
    public void dfs(String s, int index, Deque<String> path, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 枚举子串结束位置 [index, i]
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                path.addLast(s.substring(index, i + 1));
                dfs(s, i + 1, path, res);
                path.pollLast();
            }
        }
    }

    public void dfs1(String s, int index, int start, Deque<String> path, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 不选 index
        if (index < s.length() - 1) {
            dfs1(s, index + 1, start, path, res);
        }

        // 选 index
        if (isPalindrome(s, start, index)) {
            path.addLast(s.substring(start, index + 1));
            dfs1(s, index + 1, index + 1, path, res);
            path.pollLast();
        }
    }

    public boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}
